package leetcode_600;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 *@author 周杨
 *NextGreaterElementII_503 循环数组 判断下一个比其大的 但是数组有重复的
 *describe:hash存储index 并且栈遍历两次 AC 45%
 *2018年9月5日 下午9:57:51
 */
public class NextGreaterElementII_503 {
	public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack=new Stack<Integer>();
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;++i) {
        	while(!stack.isEmpty()&&nums[i]>nums[stack.peek()]) {
        		map.put(stack.pop(),nums[i]);
        	}
        	stack.push(i);
        }
        /*for(int num:nums) {
        	while(!stack.isEmpty()&&num>stack.peek()) {
        		map.put(stack.pop(), num);
        	}
        	stack.push(num);
        }*/
        for(int i=0;i<nums.length;++i) {
        	while(!stack.isEmpty()&&nums[i]>nums[stack.peek()]) {
        		map.put(stack.pop(), nums[i]);
        	}
        }
        for(int i=0;i<nums.length;++i) {
        	nums[i]=map.getOrDefault(i, -1);
        }
        return nums;
    }
}
